package testing.src.vineet.java.code.tree;

import testing.src.vineet.java.code.node.DoubleNode;
import testing.src.vineet.java.code.node.Node;

public class BinaryTree
{
	private DoubleNode root ;
	
	public BinaryTree(int value)
	{
		this.root = new DoubleNode(value) ;
		this.root.setLeft(null);
		this.root.setRight(null);
	}
	
	public DoubleNode getRoot() {
		return root;
	}

	private void preOrder(DoubleNode parent)
	{
		if(parent!=null)
		{
			System.out.print(parent.getData()+"=> ");
			preOrder(parent.getLeft());
			preOrder(parent.getRight());
		}
	}
	private void postOrder(DoubleNode parent)
	{
		if(parent!=null)
		{
		    postOrder(parent.getLeft());
		    postOrder(parent.getRight());
			System.out.print(parent.getData()+"=> ");
		}
	}
	private void inOrder(DoubleNode parent)
	{
		if(parent!=null)
		{
		    inOrder(parent.getLeft());
			System.out.print(parent.getData()+"=> ");
			inOrder(parent.getRight());
		}
	}
	//To move a non-leaf node down in the tree, we either swap it with the smallest key in the right subtree or with the largest one in the left subtree. 
	private void remove(int value,Node parent)
	{
		
	}
	public void remove(int value)
	{
		
	}
	
	public DoubleNode search(int value)
	{
		DoubleNode tmp = this.root;
		while(tmp != null)
		{
			if(value < tmp.getData())
			{
				tmp = tmp.getLeft();
			}
			else if(value > tmp.getData())
			{
				tmp = tmp.getRight();
		    }
			else
			{
				return tmp;
			}
		}
		return tmp;
	}
	public DoubleNode findSmallest()
	{
		DoubleNode tmp = this.root ;
		if(tmp != null)
		{
			while(tmp.getLeft()!= null)
			{
				tmp = tmp.getLeft();
			}
		}
		
		return tmp;
	}
	public DoubleNode findSmallest(DoubleNode parent)
	{
		DoubleNode tmp = parent ;
		if(tmp != null)
		{
			while(tmp.getLeft()!= null)
			{
				tmp = tmp.getLeft();
			}
		}
		
		return tmp;
	}
	public DoubleNode findLargest()
	{
		DoubleNode tmp = this.root ;
		if(tmp != null)
		{
			while(tmp.getRight()!=null)
			{
				tmp = tmp.getRight();
			}
		}
		return tmp;
	}
	public DoubleNode findLargest(DoubleNode parent)
	{
		DoubleNode tmp = parent;
		if(tmp != null)
		{
			while(tmp.getRight()!=null)
			{
				tmp = tmp.getRight();
			}
		}
		return tmp;
	}
	private int height(DoubleNode parent)
	{
		if(parent == null)
		{
			return -1;
		}
		else if(parent.getLeft() == null && parent.getRight() == null)
		{
			return 0;
		}
		else
		{
			int hleft = height(parent.getLeft());
			int hright = height(parent.getRight());
			return (hleft > hright ? hleft : hright) + 1;
		}
	}
	
	public int height()
	{
		return height(this.root);
	}
	private void insert(int value,DoubleNode parent)
	{
		if(value < parent.getData())
		{
			if(parent.getLeft() != null)
			{
				insert(value,parent.getLeft());
			}
			else
			{
				DoubleNode tmp = new DoubleNode(value);
				tmp.setLeft(null);
				tmp.setRight(null);
				parent.setLeft(tmp);
			}
		}
		else if(parent.getData() < value)
		{
			if(parent.getRight() != null)
			{
				insert(value, parent.getRight());
			}
			else
			{
				DoubleNode tmp = new DoubleNode(value);
				tmp.setLeft(null);
				tmp.setRight(null);
				parent.setRight(tmp);
			}
		}
	}

	public void insert(int value){
	    this.insert(value, this.root);
	}

	public void preOrder(){
	    this.preOrder(this.root);
	}
	public void postOrder(){
        this.postOrder(this.root);
    }
	public void inOrder(){
        this.inOrder(this.root);
    }
}
